Wireless mesh network deployments are popular as a cost-effective means to provide broadband connectivity to large user populations. For instance, wireless mesh networks are being deployed in many cities in order to provide ubiquitous Internet access. Thus, wireless mesh networks provide citywide wireless coverage through the careful deployment of mesh nodes. Each node provides coverage to a nearby region, while using multi-hop transmission to connect to an Internet gateway node. Multi-hop means that a signal can move from mesh node-to-mesh node and then finally to the Internet gateway node rather than from the user directly to the gateway node. A mesh network's gateway nodes that connect the wireless mesh network with the wired Internet are critical capacity points as their location and quantity determine the maximum throughput supported by the mesh network.
Selecting optimal install locations of mesh nodes is difficult. One of the challenges is that a mesh node location must jointly satisfy connectivity and coverage constraints. Connectivity means that mesh nodes are interconnected to communicate with each other, and coverage means that a client can connect to a mesh node in a target area. A connectivity constraint may be that each mesh node is required to be connected directly (e.g., via one hop) or indirectly (e.g., via multi-hops) with every other mesh node in the mesh network. A coverage constraint may be a signal strength requirement for a client in any location within a target geographic area. In addition to having to meet constraints when selecting mesh node locations, there may be a very large number of potential mesh node locations to choose. If testing is performed at every location to determine whether constraints are satisfied, deployment costs may increase.